#include<bits/stdc++.h>
#define PP pair<int,pair<int,int> > 
using namespace std;
int fa[400011];
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int T;
int n,m;
set<int> S,qs;
int s[400011],id;
int pre[400011];
priority_queue<PP,vector<PP >,greater<PP > > e;
pair<int,pair<int,int> > ed[100011];
map<int,int> mp;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	cin >> T;
	while(T--)
	{
		mp.clear(),S.clear(),qs.clear(),id = 0;
		S.insert(1);
		cin >> n >> m;
		for(int i = 1;i <= m;i++)
		{
			int x,y,w;
			cin >> x >> y >> w;
			ed[i] = {w,{x,y}};
			qs.insert(x),qs.insert(y);
			S.insert(x);
			if(x < n) S.insert(x + 1);
			S.insert(y);
			if(y < n) S.insert(y + 1);
		}
		for(auto x:S)
			s[mp[x] = ++id] = x;
		for(int i = 1;i <= id;i++)
			pre[i] = pre[i - 1] + (qs.find(s[i]) == qs.end());
		s[id + 1] = n + 1;
		long long ans = 0;
		for(int i = 1;i <= id;i++) if(pre[i] != pre[i - 1])
			ans += (s[i + 1] - s[i]) - 1;
		for(int i = 1;i <= id;i++)
			fa[i] = i;
		int l = 0;
		for(int i = 1;i <= id;i++)
		{
			if(pre[i] == pre[i - 1])
			{
				if(l)
					e.push({s[i] - s[l + 1] + 1,{l,i}});
			}else{
				l = i;
			}
		}
		l = 0;
		for(int i = id;i;i--)
		{
			if(pre[i] == pre[i - 1])
			{
				if(l)
					e.push({s[l] - s[i + 1] + 1,{l,i}});
			}else{
				l = i;
			}
		}
		for(int i = 1;i <= m;i++)
			e.push({ed[i].first,{mp[ed[i].second.first],mp[ed[i].second.second]}});
		while(!e.empty())
		{
			int x = e.top().second.first,y = e.top().second.second,w = e.top().first;
			e.pop();
			if((x = find(x)) == (y = find(y)))
				continue;
			cerr << x << " " << y << " " << w << "\n";
			ans += w;
			fa[x] = y;
		}
		cout << ans << "\n";
	}
	return 0;
}